package com.itheima.algorithm.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 组合总和 III - 回溯
 */
public class PermuteLeetcode216 {

    static List<List<Integer>> combinationSum3(int k, int target) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(1, k, target, new LinkedList<>(), result);
        return result;
    }

//    static int count = 0;

    static void dfs(int start, int k, int target,
                    LinkedList<Integer> stack,
                    List<List<Integer>> result) {
//        count++;
        if (0 == target && k == stack.size()) {
            result.add(new ArrayList<Integer>(stack));
            return;
        }
        for (int i = start; i <= 9; i++) {
            if (target < i) {
                continue;
            }
            if (k - stack.size() > 9 - i + 1) { // 剪枝
                continue;
            }
            if (k == stack.size()) {
                continue;
            }
            stack.push(i);
            dfs(i + 1, k, target - i, stack, result);
            stack.pop();
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = combinationSum3(3, 7);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
//        System.out.println("count = " + count);
    }
}
